package main

/*
四种状态：
1. 不操作，沿用之前的值
2. 第一次买入，取第一次买入和第一次未买入-当前股票的最大值
3. 第一次卖出，max（第一次买入+当前股票，第一次卖出）
4. 第二次买入
5. 第二次卖出
*/
func maxProfit(prices []int) int {
	dp := make([][]int, 5)
	for i := range dp {
		dp[i] = make([]int, len(prices))
	}

	dp[1][0] = -prices[0]
	dp[3][0] = -prices[0]

	for i := 1; i < len(prices); i++ {
		dp[0][i] = dp[0][i-1]
		dp[1][i] = max123(dp[0][i-1]-prices[i], dp[1][i-1])
		dp[2][i] = max123(dp[2][i-1], dp[1][i-1]+prices[i])
		dp[3][i] = max123(dp[2][i-1]-prices[i], dp[3][i-1])
		dp[4][i] = max123(dp[4][i-1], dp[3][i-1]+prices[i])
	}
	return dp[4][len(prices)-1]
}

func max123(a, b int) int {
	if a > b {
		return a
	}
	return b
}
